// https://leetcode.cn/problems/successor-lcci/
// 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。如果指定节点没有对应的“下一个”节点，则返回null。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:

	// 先中序遍历，再挨个查找，这是最笨的方法
    struct TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
		vector<TreeNode *> res;
		show(root, res);
		int len = res.size();
		for(int i = 0; i < len; i++){
			if(res[i] == p && i < len-1){
				return res[i+1];
			}
		}
		return nullptr;
    }
	
	void show(TreeNode* root, vector<TreeNode *> &res){
		if(root){
			show(root->left, res);
			res.push_back(root);
			show(root->right, res);
		}
	}
	
	/**
	总体的要旨：找到第一个大于root->val值的节点
	
	根据二叉搜索树的性质，其中序遍历是单调递增的；

	若当前节点值小于等于给定节点值，说明给定的节点在当前节点的右子树中；

	若当前节点值大于给定节点值，则分两种情况讨论：
	1、当前节点就是给定节点的后继者；
	2、若当前节点存在左子树，则当前节点左子树中最左的节点才是给定节点的后继者。
	
			 10
		5		 15
	  3   7   13    17
	  
	  输出顺序 3,5,7,10,13,15,17
	*/
	struct TreeNode* inorderSuccessor1(TreeNode* root, TreeNode* p) {
		if(root == nullptr){
			return nullptr;
		}
		if(root->val <= p->val){ // 说明在右子树
			return inorderSuccessor1(root->right, p);
		}else{
			// 说明在左子树或者是root节点
			auto left = inorderSuccessor1(root->left, p);
			return left ? left : root;
		}
    }
	
	TreeNode* inorderSuccessor2(TreeNode* root, TreeNode* p) {
        if (!root) return nullptr;
        if (root->val <= p-> val)
            return inorderSuccessor2(root->right, p);
        TreeNode* findLeft = inorderSuccessor2(root->left, p);
        return findLeft ? findLeft : root;
    }
	
	/*
			 10
		5		 15
	  3   7   13    17
	  
	  输出顺序 3,5,7,10,13,15,17
	*/

	struct TreeNode* init(){
		struct TreeNode * head = new TreeNode(10);
		
		struct TreeNode * n1 = new TreeNode(5);
		head->left = n1;
		
		struct TreeNode * n2 = new TreeNode(15);
		head->right = n2;
		
		struct TreeNode * n3 = new TreeNode(3);
		n1->left = n3;
		
		struct TreeNode * n4 = new TreeNode(7);
		n1->right = n4;
		
		struct TreeNode * n5 = new TreeNode(13);
		n2->left = n5;
		
		struct TreeNode * n6 = new TreeNode(17);
		n2->right = n6;
		
		return head;
	}
	
};

int main(){
	Solution so;
	struct TreeNode * head= so.init();
	TreeNode * h1 = head; // 7
	cout << "head:" << h1->val << endl;
	// TreeNode * n1 = head->left; // 5
	struct TreeNode * find = so.inorderSuccessor1(head, h1);
	if(find){
		cout << find->val << endl;
	}
	else{
		cout << "not found" << endl;
	}
	
	return 0;
}